class Solution {
public:
    int maxNumberOfAlloys(int m, int n, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {
        int l = 0, r = 1e9;
        auto check = [&](long long x) -> bool {
            for (int i = 0; i < n; i++) {
                vector<long long>temp(m + 1);
                for (int j = 0; j < m; j++) {
                    temp[j] = x * (long long)composition[i][j] - stock[j];
                }
                long long ans = 0;
                for (int j = 0; j < m; j++) {
                    ans += max(temp[j] * (long long)cost[j], 1ll * 0);
                }
                if (ans <= budget)return true;
            }
            return false;
        };
        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            if (check(mid))l = mid;
            else r = mid;
        }
        return l;
    }
};

